package com.example.algorithm.sort.quick;

import com.example.algorithm.sort.BaseSort;

/**
 * @program: algorithm
 * @description:快速排序
 * @packagename: com.example.algorithm.sort.quick
 * @author: Jay
 * @date: 2022/03/27 23:17:03
 **/
public class Quick extends BaseSort {

    /**
     * 对数组a元素进行排序
     * @param a
     */
    public static void sort(Comparable[] a){

        int lo = 0;
        int hi = a.length - 1;
        sort(a,lo,hi);
    }

    /**
     * 对数组a从索引lo到索引hi之间的元素进行排序
     * @param a
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a, int lo, int hi) {
        //安全性校验
        if (hi <= lo){
            return;
        }

        //需要对数组中lo索引到hi索引处的元素进行分组（左子组和右子组）
        int partition = partition(a,lo,hi);//返回的是分界值所在的索引，分界值变换后的索引

        //让左子组有序
        sort(a,lo,partition - 1);

        //让右子组有序
        sort(a,partition + 1, hi);

    }

    private static int partition(Comparable[] a, int lo, int hi) {
        //确定分界值
        Comparable key = a[lo];
        //定义两个指针，分别指向待切分元素最小索引处和最大索引处的下一个位置
        int left = lo;
        int right = hi + 1;

        //切分
        while (true){
            //先从右往左扫描，移动right指针，找一个比分界值小的停止
            while (less(key,a[--right])){
                if (right == lo){
                    break;
                }
            }
            //从左往右扫描，移动left指针，找比分界值大的值停止
            while (less(a[++left],key)){
                if (left == hi){
                    break;
                }
            }
            //判断left >= right,如果是，则证明元素扫描完毕，结束循环，如果不是则交换元素
            if (left >= right){
                break;
            }else {
                exch(a,left,right);
            }
        }

        //交换分界值
        exch(a,lo,right);

        return right;
    }
}
